Thuật toán tối ưu là gì? Các nghiên cứu khoa học liên quan

Định nghĩa thuật toán tối ưu

Thuật toán tối ưu là một thủ tục tính toán nhằm tìm ra giá trị đầu vào tối ưu của một bài toán, sao cho hàm mục tiêu đạt cực trị (tối thiểu hoặc tối đa) dưới các điều kiện xác định. Đây là trung tâm của rất nhiều ứng dụng trong toán học ứng dụng, kỹ thuật, khoa học máy tính, tài chính định lượng và học máy. Việc lựa chọn thuật toán phù hợp với loại bài toán cụ thể có ảnh hưởng lớn đến hiệu quả tính toán và độ chính xác của lời giải.

Trong dạng tổng quát nhất, bài toán tối ưu có thể biểu diễn như sau:

$\min_{x \in \mathbb{R}^n} f(x)$

Trong đó:

• $x \in \mathbb{R}^n$: biến quyết định
• $f(x)$: hàm mục tiêu cần tối ưu

Tùy vào mục tiêu cụ thể, bài toán có thể được chuyển đổi sang bài toán tối đa bằng cách tối thiểu hóa hàm $-f(x)$. Trong thực tế, bài toán còn có thể kèm theo các ràng buộc dạng đẳng thức hoặc bất đẳng thức, khiến cho việc tìm nghiệm trở nên phức tạp hơn nhiều.

Phân loại thuật toán tối ưu

Có nhiều cách phân loại thuật toán tối ưu tùy theo bản chất của bài toán, cấu trúc dữ liệu, hoặc tính chất của không gian tìm kiếm. Một số tiêu chí phân loại cơ bản như sau:

• Theo tính chất bài toán: liên tục hoặc rời rạc
• Theo khả năng đạo hàm: khả vi hoặc phi khả vi
• Theo chiến lược tìm kiếm: xác định (deterministic) hoặc ngẫu nhiên (stochastic)
• Theo phạm vi nghiệm: tối ưu cục bộ hoặc toàn cục

Ví dụ:

• Gradient Descent là thuật toán xác định, hoạt động tốt trên bài toán liên tục, khả vi
• Genetic Algorithm là thuật toán ngẫu nhiên, phù hợp với bài toán rời rạc, phi tuyến

Bảng sau minh họa một số thuật toán phổ biến theo nhóm:

Nhóm bài toán	Thuật toán tiêu biểu	Đặc điểm
Tối ưu liên tục	Gradient Descent, Newton's Method	Cần đạo hàm, hội tụ nhanh với bài toán lồi
Tối ưu rời rạc	Genetic Algorithm, Simulated Annealing	Không cần đạo hàm, áp dụng cho không gian tổ hợp
Tối ưu toàn cục	Bayesian Optimization	Giải bài toán phức tạp không khả vi, tốn chi phí đánh giá

Tối ưu không ràng buộc và có ràng buộc

Tùy vào điều kiện của bài toán, người ta chia thành hai loại chính: tối ưu không ràng buộc và tối ưu có ràng buộc. Với tối ưu không ràng buộc, ta tìm cực trị của hàm mục tiêu trong toàn bộ không gian biến, không có giới hạn. Trong khi đó, tối ưu có ràng buộc đặt thêm các điều kiện dạng bất đẳng thức hoặc đẳng thức giới hạn phạm vi của nghiệm.

Biểu thức tổng quát của bài toán tối ưu có ràng buộc:

$\begin{aligned} \min_{x \in \mathbb{R}^n} \quad & f(x) \\ \text{subject to} \quad & g_i(x) \leq 0,\quad i=1,\dots,m \\ & h_j(x) = 0,\quad j=1,\dots,p \end{aligned}$

Trong đó:

• $g_i(x)$: ràng buộc bất đẳng thức
• $h_j(x)$: ràng buộc đẳng thức

Các phương pháp giải bài toán có ràng buộc bao gồm: phương pháp nhân tử Lagrange (Lagrange multipliers), phương pháp rào cản (barrier methods), phương pháp điểm nội (interior-point), và thuật toán tối ưu tuần tự (SQP - Sequential Quadratic Programming).

Thuật toán tối ưu lồi

Bài toán tối ưu lồi là loại bài toán trong đó hàm mục tiêu là một hàm lồi và tập nghiệm khả thi cũng là tập lồi. Tính chất này đảm bảo rằng mọi điểm cực trị cục bộ đều là cực trị toàn cục, giúp việc tối ưu hóa dễ dàng và có thể chứng minh nghiệm duy nhất.

Các phương pháp giải hiệu quả cho bài toán lồi bao gồm:

• Gradient Descent (giảm dần theo đạo hàm)
• Newton's Method (sử dụng đạo hàm bậc hai)
• Phương pháp nội điểm (Interior-Point Method)

Một ví dụ kinh điển là bài toán hồi quy Ridge:

$\min_{w} \left\| Xw - y \right\|_2^2 + \lambda \left\| w \right\|_2^2$

Bài toán này có nghiệm duy nhất, được dùng rộng rãi trong học máy để xử lý hiện tượng quá khớp (overfitting). Tính chất lồi cho phép ta sử dụng các kỹ thuật gradient hiệu quả và hội tụ nhanh chóng. Chi tiết xem tại Convex Optimization – Boyd & Vandenberghe.

Thuật toán tối ưu phi lồi

Tối ưu phi lồi là bài toán trong đó hàm mục tiêu hoặc/hoặc tập ràng buộc không có tính chất lồi. Điều này dẫn đến sự tồn tại của nhiều điểm cực trị cục bộ, khiến cho việc tìm nghiệm toàn cục trở nên phức tạp và không có bảo đảm chắc chắn về tính tối ưu toàn cục của nghiệm tìm được.

Trong các mô hình mạng nơ-ron sâu (deep neural networks), hàm mất mát thường có hình dạng phi lồi, bao gồm nhiều điểm yên ngựa, cực tiểu cục bộ và mặt cong phức tạp. Điều này khiến thuật toán tìm nghiệm dựa trên gradient dễ bị “kẹt” trong cực trị cục bộ, đặc biệt khi khởi tạo không phù hợp.

Một số kỹ thuật thường dùng để xử lý tối ưu phi lồi:

• Khởi tạo nhiều lần tại các điểm khác nhau (multi-start strategy)
• Thêm nhiễu vào gradient hoặc dữ liệu huấn luyện
• Sử dụng các phương pháp ngẫu nhiên như thuật toán di truyền, mô phỏng tôi luyện

Thuật toán tối ưu trong học sâu

Trong học sâu (deep learning), quá trình huấn luyện mô hình thực chất là giải một bài toán tối ưu phi lồi, nơi hàm mục tiêu là hàm mất mát giữa dự đoán của mô hình và nhãn thực tế. Các thuật toán tối ưu dựa trên gradient là công cụ cốt lõi để cập nhật tham số mô hình theo hướng giảm hàm mất mát.

Thuật toán gradient descent cơ bản được cập nhật theo công thức:

$\theta_{t+1} = \theta_t - \eta \nabla_\theta \mathcal{L}(\theta_t)$

Trong đó:

• $\theta_t$: vector tham số tại bước $t$
• $\eta$: tốc độ học (learning rate)
• $\mathcal{L}$: hàm mất mát (loss function)

Các biến thể nâng cao bao gồm:

• Stochastic Gradient Descent (SGD): sử dụng mini-batch, giúp cập nhật nhanh và tiết kiệm bộ nhớ
• Adam: tích hợp động lượng và điều chỉnh tốc độ học thích ứng theo từng tham số
• RMSprop: sử dụng trung bình bình phương gradient để điều chỉnh tốc độ học

Chi tiết hơn về các thuật toán này có thể xem tại Sebastian Ruder - Optimizing Gradient Descent.

Thuật toán tối ưu rời rạc và tổ hợp

Tối ưu tổ hợp (combinatorial optimization) liên quan đến các bài toán mà không gian nghiệm là tập rời rạc, hữu hạn nhưng cực lớn. Đây là dạng bài toán đặc biệt khó do không thể áp dụng các phương pháp đạo hàm thông thường. Tối ưu tổ hợp có mặt trong nhiều bài toán kinh điển như:

• Bài toán người du lịch (TSP)
• Bài toán lập lịch (Job Scheduling)
• Bài toán đóng gói (Knapsack Problem)

Một số thuật toán phổ biến để giải các bài toán này:

• Thuật toán quay lui (backtracking), nhánh và cận (branch and bound)
• Heuristic: thuật toán tham lam, tìm kiếm cục bộ
• Metaheuristic: mô phỏng tôi luyện (simulated annealing), thuật toán di truyền (genetic algorithm), bầy đàn (particle swarm)

Nguồn tham khảo chi tiết: ScienceDirect - Combinatorial Optimization

Hiệu suất và tiêu chí đánh giá thuật toán

Việc đánh giá thuật toán tối ưu không chỉ dựa trên khả năng tìm được nghiệm mà còn ở nhiều khía cạnh thực tế khác. Một số tiêu chí phổ biến bao gồm:

• Tốc độ hội tụ: số vòng lặp cần để đạt tới nghiệm chấp nhận được
• Độ chính xác: sai số so với giá trị tối ưu lý tưởng
• Tính ổn định: mức độ nhạy cảm với nhiễu và điều kiện khởi tạo
• Chi phí tính toán: thời gian và bộ nhớ tiêu tốn

Việc lựa chọn thuật toán tối ưu tốt nhất phụ thuộc vào bài toán cụ thể, quy mô dữ liệu, tài nguyên tính toán và yêu cầu về độ chính xác hay tốc độ. Trong học máy, tốc độ huấn luyện có thể quan trọng hơn nghiệm chính xác tuyệt đối.

Ứng dụng thực tiễn của thuật toán tối ưu

Thuật toán tối ưu được ứng dụng trong nhiều lĩnh vực thực tiễn, từ công nghiệp đến công nghệ số. Một số ứng dụng tiêu biểu:

• Học máy: huấn luyện mô hình, tối ưu siêu tham số (hyperparameter tuning)
• Vận tải - logistics: định tuyến giao hàng, tối ưu hóa lịch trình
• Tài chính: tối ưu danh mục đầu tư, quản lý rủi ro
• Kỹ thuật: thiết kế cấu trúc, điều khiển robot, hệ thống điều hòa tự động

Ví dụ, trong CVXPY – một thư viện Python dùng để giải bài toán tối ưu – các thuật toán như interior-point, conic programming được sử dụng để thiết kế hệ thống năng lượng tái tạo hoặc tối ưu vận hành pin lưu trữ.

Tài liệu tham khảo

1. Boyd, S., & Vandenberghe, L. (2004). Convex Optimization. Cambridge University Press. Link
2. Ruder, S. (2017). "An overview of gradient descent optimization algorithms." ruder.io
3. Bertsekas, D. P. (1999). Nonlinear Programming. Athena Scientific.
4. Nocedal, J., & Wright, S. J. (2006). Numerical Optimization. Springer.
5. Mitchell, M. (1998). An Introduction to Genetic Algorithms. MIT Press.
6. Floudas, C. A., & Pardalos, P. M. (2001). Encyclopedia of Optimization. Springer.
7. ScienceDirect. "Combinatorial Optimization." Link
8. Diamond, S., & Boyd, S. (2016). "CVXPY: A Python-Embedded Modeling Language for Convex Optimization." cvxpy.org